package dp.备忘录dfs;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 整数拆分343.java
 * @createTime 2024年03月27日 09:50:00
 */
public class 整数拆分343 {
	/*
F(n)= math.max(i*(n-1),F(n-i)*i)
 */
	int[] memo;

	public int integerBreak(int n) {
		memo = new int[n + 1];
        /*if (n == 2) {
            return 1;
        }
        int res = -1;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, Math.max(i * (n - i), integerBreak(n - i) * i));
        }*/
		return dp(n);
	}

	public int dp(int n) {
		if (n == 2) {
			return 1;
		}
		if (memo[n]!=0){
			return memo[n];
		}
		int res = -1;
		for (int i = 1; i < n; i++) {
			res = Math.max(res, Math.max(i * (n - i), dp(n - i) * i));
		}
		memo[n]=res;
		return res;
	}
}
